Maximum Subarray (LeetCode 53, Kadane’s Algorithm)

解題思路

1. 動態規劃：

• dp[i] = 以 nums[i] 結尾的最大子陣列和
• 遞推式：dp[i] = max(nums[i], dp[i-1] + nums[i])
• Kadane’s Algorithm → O(n) 時間，O(1) 空間

2. Kotlin 解法

class Solution {
    fun maxSubArray(nums: IntArray): Int {
        var maxSoFar = nums[0]
        var curr = nums[0]
        for (i in 1 until nums.size) {
            curr = maxOf(nums[i], curr + nums[i])
            maxSoFar = maxOf(maxSoFar, curr)
        }
        return maxSoFar
    }
}

3. Follow-up

• 如果要輸出實際的子陣列？
• 如果陣列長度很大，如何做分治 (Divide & Conquer)？
• 如果陣列是 2D，怎麼處理？（最大子矩陣和 → 進階題）